/////////////////////////////////////////////////////////////////////////
//
// Amuse Engine SDK - core/containers
// Copyright( c) 2014.  All Rights Reserved
//
// File:		AEBaseMap.inl
// Author:		Gianluca Belardelli
// Date:		07/05/2014
//
/////////////////////////////////////////////////////////////////////////
#ifndef _AEBASEMAP_INL_
#define _AEBASEMAP_INL_

static const AEUINT32 sg_uiMinimumCapacity = 8;

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE typename AEBaseMap<KEY,VAL,OPS>::AEMapIterator AEBaseMap<KEY,VAL,OPS>::GetIterator( void ) const
{
	AEINT32 i;
	for( i = 0; i <= m_nHashMod; ++i )
	{
		if( OPS::IsValid( m_mpElem[i].tKey ) )
			break;
	}
	
	return AE_MAP_INDEX_TO_ITERATOR(i);
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE KEY AEBaseMap<KEY,VAL,OPS>::GetKey( AEMapIterator miIterator ) const
{
	AEINT32 i = AE_MAP_ITERATOR_TO_INDEX( miIterator );
	AEASSERT( i >= 0 && i <= m_nHashMod);

	return m_mpElem[i].tKey;
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE VAL AEBaseMap<KEY,VAL,OPS>::GetValue( AEMapIterator miIterator ) const
{
	AEINT32 i = AE_MAP_ITERATOR_TO_INDEX( miIterator );
	AEASSERT( i >= 0 && i <= m_nHashMod);

	return m_mpElem[i].tVal;
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE void AEBaseMap<KEY,VAL,OPS>::SetValue( AEMapIterator miIterator, VAL tVal )
{
	AEINT32 i = AE_MAP_ITERATOR_TO_INDEX( miIterator );
	AEASSERT( i >= 0 && i <= m_nHashMod);

	m_mpElem[i].tVal = tVal;
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE typename AEBaseMap<KEY,VAL,OPS>::AEMapIterator AEBaseMap<KEY,VAL,OPS>::GetNext( AEMapIterator miIterator ) const
{
	AEINT32 i = AE_MAP_ITERATOR_TO_INDEX( miIterator );
	AEASSERT( i >= 0 && i <= m_nHashMod);
	
	for( i += 1; i <= m_nHashMod; ++i )
	{
		if( OPS::isValid( m_mpElem[i].tKey ) )
			break;
	}

	return AE_MAP_INDEX_TO_ITERATOR(i);
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE AEBOOL32 AEBaseMap<KEY,VAL,OPS>::IsValid( AEMapIterator it ) const
{
	// range [0, hashMod] is valid
	// hashMod+1 invalid
	// anything else is bad input
	AEINT32 i = AE_MAP_ITERATOR_TO_INDEX(it);
	AEASSERT( i >= 0 && i <= m_nHashMod+1 );

	return i <= m_nHashMod;
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE AEBOOL32 AEBaseMap<KEY,VAL,OPS>::isPower2( AEUINT32 uiVal )
{
	return ( uiVal & ( uiVal - 1 ) ) == 0;
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE AEINT32 AEBaseMap<KEY,VAL,OPS>::GetSize( void ) const
{
	return m_nNumElems & static_cast<AEINT32>( NUM_ELEMS_MASK );
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE AEINT32 AEBaseMap<KEY,VAL,OPS>::GetCapacity( void ) const
{
	return ( m_nHashMod + 1 ) & static_cast<AEINT32>( NUM_ELEMS_MASK );
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE void *AEBaseMap<KEY,VAL,OPS>::GetMemStart( void ) const
{
	return m_mpElem;
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE AEBOOL32 AEBaseMap<KEY,VAL,OPS>::WasReallocated( void ) const
{
	return ( ( m_nNumElems & static_cast<AEINT32>( DONT_DEALLOCATE_FLAG ) ) == 0 );
}

template < typename KEY, typename VAL, typename OPS >
AE_FORCEINLINE AEBOOL32 AEBaseMap<KEY,VAL,OPS>::HasKey( KEY tKey ) const
{
	return IsValid( FindKey( tKey ) );
}

template < typename KEY, typename VAL, typename OPS >
AEBaseMap<KEY,VAL,OPS>::AEBaseMap( void* lpPtr, AEINT32 nSizeInBytes )
{
	Init( lpPtr, nSizeInBytes );
}

template < typename KEY, typename VAL, typename OPS >
AEBaseMap<KEY,VAL,OPS>::~AEBaseMap( void )
{
	AEASSERT_MSG( ( m_nNumElems & DONT_DEALLOCATE_FLAG ) || ( m_mpElem == 0L ), "memory not freed" );
}

template < typename KEY, typename VAL, typename OPS >
AEBOOL32 AEBaseMap<KEY,VAL,OPS>::Insert( AEMemoryAllocator &maAlloc, KEY tKey, VAL tVal )
{
	AEASSERT_MSG( OPS::IsValid( (KEY)tKey ), "Pointer map keys must not be the empty value" );
	{
		AEINT32 nNumElems = m_nNumElems & static_cast<AEINT32>( NUM_ELEMS_MASK );
		if( ( nNumElems + nNumElems ) > m_nHashMod )
		{
			resizeTable( maAlloc, m_nHashMod + m_nHashMod + 2 );
		}
	}
	
	AEUINT32 i;
	AEBOOL32 isNewKey = true;
	for( i = OPS::Hash( (KEY)tKey, m_nHashMod ); OPS::IsValid( (KEY)m_mpElem[i].tKey ); i = ( i+1 ) & m_nHashMod )
	{
		// find free slot
		if( OPS::Equal( (KEY)m_mpElem[i].tKey, (KEY)tKey ) )
		{
			isNewKey = false;
			break;
		}
	}

	// dont increment m_nNumElems if overwriting.
	m_nNumElems += isNewKey;

	// insert tKey,value
	m_mpElem[i].tKey = tKey;
	m_mpElem[i].tVal = tVal;
	return isNewKey;
}

template < typename KEY, typename VAL, typename OPS >
AEBOOL32 AEBaseMap<KEY,VAL,OPS>::TryInsert( AEMemoryAllocator &maAlloc, KEY tKey, VAL tVal, AEUINT32 &uiRes )
{
	AEASSERT_MSG( OPS::IsValid( tKey ), "Pointer map keys must not be the empty value" );
	// This is quite conservative. We could grow more
	// slowly at the cost of potentially longer searches.
	{
		AEINT32 nNumElems = m_nNumElems & static_cast<AEINT32>( NUM_ELEMS_MASK );
		if( ( nNumElems + nNumElems ) > m_nHashMod )
		{
			uiRes = resizeTable( maAlloc, m_nHashMod + m_nHashMod + 2 );
			if( uiRes != 1 )
				return false;
		}
		else
		{
			uiRes = 1;
		}
	}
	
	return Insert( maAlloc, tKey, tVal );
}

template < typename KEY, typename VAL, typename OPS >
typename AEBaseMap<KEY,VAL,OPS>::AEMapIterator AEBaseMap<KEY,VAL,OPS>::FindKey( KEY tKey ) const
{
	if( m_nHashMod > 0 )
	{
		for( AEUINT32 i = OPS::Hash( (KEY)tKey, m_nHashMod ); OPS::IsValid( (KEY)m_mpElem[i].tKey ); i = ( i+1 ) & m_nHashMod )
		{
			if( OPS::Equal( (KEY)m_mpElem[i].tKey, (KEY)tKey ) )
				return AE_MAP_INDEX_TO_ITERATOR( i ); // found
		}
	}

	return AE_MAP_INDEX_TO_ITERATOR( m_nHashMod + 1 ); // not found
}

template < typename KEY, typename VAL, typename OPS >
typename AEBaseMap<KEY,VAL,OPS>::AEMapIterator AEBaseMap<KEY,VAL,OPS>::FindOrInsertKey( AEMemoryAllocator &maAlloc, KEY tKey, VAL tVal )
{
	AEASSERT_MSG( OPS::IsValid( (AEINT32)tKey ), "Pointer map keys must not be the empty value" );

	// reserve space for another element
	AEINT32 nNumElems = m_nNumElems & static_cast<AEINT32>( NUM_ELEMS_MASK );
	if( ( nNumElems + nNumElems ) > m_nHashMod )
	{
		resizeTable( maAlloc, m_nHashMod + m_nHashMod + 2 );
	}

	AEUINT32 i;
	for( i = OPS::Hash( (AEINT32)tKey, m_nHashMod ); true;	i = ( i + 1 ) & m_nHashMod )
	{
		if( OPS::Equal( (AEINT32)m_mpElem[i].tKey, (AEINT32)tKey ) )
			return AE_MAP_INDEX_TO_ITERATOR(i); // found

		else if( !OPS::IsValid( (AEINT32)m_mpElem[i].tKey ) ) // end of chain, insert
		{
			m_mpElem[i].tKey = tKey;
			m_mpElem[i].tVal = tVal;
			m_nNumElems += 1;
			return AE_MAP_INDEX_TO_ITERATOR( i ); // new elem
		}
	}
	// notreached
}

template < typename KEY, typename VAL, typename OPS >
VAL AEBaseMap<KEY,VAL,OPS>::GetWithDefault( KEY tKey, VAL tVal ) const
{
	if( m_nHashMod > 0 )
	{
		for( AEUINT32 i = OPS::Hash( tKey, m_nHashMod ); OPS::IsValid( m_mpElem[i].tKey ); i = ( i + 1 ) & m_nHashMod )
		{
			if( OPS::Equal( m_mpElem[i].tKey, tKey ) )
				return m_mpElem[i].tVal;
		}
	}

	return tVal;
}

template < typename KEY, typename VAL, typename OPS >
AEUINT32 AEBaseMap<KEY,VAL,OPS>::Get( KEY tKey, VAL *lpOut ) const
{
	AEMapIterator miIter = FindKey( tKey );
	if( IsValid( miIter ) )
	{
		*lpOut = GetValue( miIter );
		return 1;
	}

	return 0;
}

template < typename KEY, typename VAL, typename OPS >
void AEBaseMap<KEY,VAL,OPS>::Remove( AEMapIterator miIterator )
{
	AEASSERT( IsValid( miIterator ) );
	AEASSERT( GetSize() > 0 );

	AEUINT32 i = AE_MAP_ITERATOR_TO_INDEX( miIterator );

	// remove miIter
	--m_nNumElems;
	OPS::Invalidate( m_mpElem[i].tKey );

	// find lowest element of this unbroken run
	AEUINT32 uiLowest = ( i + m_nHashMod ) & m_nHashMod;

	while( OPS::IsValid( m_mpElem[uiLowest].tKey ) )
		uiLowest = ( uiLowest + m_nHashMod ) & m_nHashMod;

	uiLowest = ( uiLowest + 1 ) & m_nHashMod;

	// the slot which has become empty
	AEUINT32 uiEmpty = i;
	
	// shift up, closing any gaps we find
	for( i = (i + 1) & m_nHashMod; OPS::IsValid( m_mpElem[i].tKey ); i = (i + 1) & m_nHashMod )
	{
		AEUINT32 uiHash = OPS::Hash( m_mpElem[i].tKey, m_nHashMod );

		// Three cases to consider here. 
		// a) The normal case where lo <= empty < i.
		// b) The case where i has wrapped around.
		// c) The case where both i and empty have wrapped around.
		// The initial case will be a. (Or b if the last slot is freed).
		// and may progress to b, and finally c.
		// The algorithm will terminate before 'i' reaches 'lo'
		// otherwise the table would have no free slots.
		
		// 'normal'      'i wrapped'   'i and empty wrapped'
		// ===== lo      ===== i       ===== empty
		// ===== empty   ===== lo      ===== i 
		// ===== i       ===== empty   ===== lo     
		
		if( ( i >= uiLowest ) && ( uiHash > uiEmpty ) )
			continue;					
		else if( ( i < uiEmpty ) && ( uiHash > uiEmpty || uiHash <= i ) )
			continue;
		else if( ( uiHash > uiEmpty && uiHash < uiLowest ) )
			continue;

		AEASSERT( i != uiEmpty ); // by design
		AEASSERT( i != uiLowest ); // table became full?!

		// copy up
		m_mpElem[uiEmpty].tKey = m_mpElem[i].tKey;
		m_mpElem[uiEmpty].tVal = m_mpElem[i].tVal;
		
		// source slot is now free
		OPS::Invalidate( m_mpElem[i].tKey );
		
		uiEmpty = i;
	}
}

template < typename KEY, typename VAL, typename OPS >
AEUINT32 AEBaseMap<KEY,VAL,OPS>::Remove( KEY tKey )
{
	AEMapIterator miIter = FindKey( tKey );
	if( IsValid( miIter ) )
	{
		Remove( miIter );
		return 1;
	}
	return 0;	
}

template < typename KEY, typename VAL, typename OPS >
AEINT32 AEBaseMap<KEY,VAL,OPS>::GetMemSize( void ) const
{
	return ( m_nHashMod + 1 ) * sizeof( AEMapPair );
}

template < typename KEY, typename VAL, typename OPS >
AEBOOL32 AEBaseMap<KEY,VAL,OPS>::IsOk( void ) const
{
	AEINT32 i, nCount = 0;

	for( i = 0; i <= m_nHashMod; ++i )
		nCount += OPS::IsValid( m_mpElem[i].tKey );

	AEASSERT( nCount == ( m_nNumElems & static_cast<AEINT32>( NUM_ELEMS_MASK ) ) );

	// is element reachable from its hash?
	for( i = 0; i <= m_nHashMod; ++i )
	{
		if( OPS::IsValid( m_mpElem[i].tKey ) )
		{
			AEUINT32 j = OPS::Hash( m_mpElem[i].tKey, m_nHashMod );
			
			while( !OPS::Equal( m_mpElem[j].tKey, m_mpElem[i].tKey ) )
			{
				j = (j + 1) & m_nHashMod;
				AEASSERT( OPS::IsValid( m_mpElem[j].tKey ) );
			}
		} 
	}
	return true;	
}

template < typename KEY, typename VAL, typename OPS >
void AEBaseMap<KEY,VAL,OPS>::Clear( void )
{
	AEINT32 nCapacity = m_nHashMod + 1;

	for( AEINT32 i = 0; i < nCapacity; i++ )
		OPS::Invalidate( (KEY &)m_mpElem[i].tKey ); 

	m_nNumElems = 0 |  (m_nNumElems & static_cast<AEINT32>( DONT_DEALLOCATE_FLAG ) );
}

template < typename KEY, typename VAL, typename OPS >
void AEBaseMap<KEY,VAL,OPS>::ClearAndDeallocate( AEMemoryAllocator &maAlloc )
{
	Clear();

	if( ( m_nNumElems & DONT_DEALLOCATE_FLAG ) == 0 )
	{
		maAlloc.BlockFree( m_mpElem, sizeof( AEMapPair ) * ( m_nHashMod + 1 ) );
		//HK_ON_DEBUG( m_nNumElems |= DONT_DEALLOCATE_FLAG );
	}

	m_mpElem = 0L; 
	m_nNumElems = 0; 
	m_nHashMod = -1;
}

template < typename KEY, typename VAL, typename OPS >
void AEBaseMap<KEY,VAL,OPS>::Reserve( AEMemoryAllocator &maAlloc, AEINT32 nNumElements )
{
	// Make sure that the actual table size is not going to be less than twice the current number of elements
	AEASSERT( nNumElements >= 0 && ( m_nNumElems & static_cast<AEINT32>( NUM_ELEMS_MASK ) ) * 2 <= nNumElements * 3 );
	AEINT32 nMinCap = nNumElements * 2;
	AEINT32 nCap = sg_uiMinimumCapacity;

	while( nCap < nMinCap )
		nCap *= 2;
	
	resizeTable( maAlloc, nCap );
}

template < typename KEY, typename VAL, typename OPS >
void AEBaseMap<KEY,VAL,OPS>::SetOwnedData( void *lpPtr, AEINT32 nSize, AEINT32 nCapacity )
{
	AEASSERT( nSize >= 0 );
	AEASSERT( nSize <= nCapacity );
	m_mpElem = static_cast<AEMapPair *>( lpPtr );
	m_nNumElems = nSize | DONT_DEALLOCATE_FLAG;
	m_nHashMod = nCapacity - 1;
}

template < typename KEY, typename VAL, typename OPS >
AEINT32 AE_CALL AEBaseMap<KEY,VAL,OPS>::GetSizeInBytesFor( AEINT32 nNumOfKeys )
{
	// adjust the number to the power of 2
	AEINT32 nNumSlots = nNumOfKeys * 2; // half full
	AEINT32 nCap;
	for( nCap = sg_uiMinimumCapacity; nCap < nNumSlots; nCap *= 2 )
	{
		// double until sufficient capacity
	}
	return nCap * sizeof( AEMapPair );
}

template < typename KEY, typename VAL, typename OPS >
void AEBaseMap<KEY,VAL,OPS>::Init( void* lpPtr, AEINT32 nSizeInBytes )
{
	AEINT32 nMaxKeys = AEUINT32( nSizeInBytes ) / ( sizeof( AEMapPair ) );

	AEASSERT( nMaxKeys >= sg_uiMinimumCapacity );
	//TODO
	//AEASSERT( IsPower2( nMaxKeys ) );
	
	m_mpElem = static_cast< AEMapPair * >( lpPtr );
	m_nNumElems = DONT_DEALLOCATE_FLAG;
	m_nHashMod = nMaxKeys - 1;
	
	AEASSERT( ( nMaxKeys * sizeof( AEMapPair ) ) == nSizeInBytes );
	
	for( AEINT32 i = 0; i < nMaxKeys; i++ )
		OPS::Invalidate( m_mpElem[i].tKey );
}

template < typename KEY, typename VAL, typename OPS >
AEUINT32 AEBaseMap<KEY,VAL,OPS>::resizeTable(AEMemoryAllocator& maAlloc, AEINT32 nNewCapacity )
{
	//TODO
	//nNewCapacity = AEMath::Max2( nNewCapacity, sg_uiMinimumCapacity );
	nNewCapacity = 128;
	
	AEASSERT_MSG( m_nNumElems < nNewCapacity, "Table size is not big enough" );
	AEASSERT_MSG( AE_NEXT_MULTIPLE_OF( 2, nNewCapacity ) == nNewCapacity, "Table size should be a power of 2" );
	
	AEBOOL32 bDontDeallocate = m_nNumElems & static_cast<AEINT32>( DONT_DEALLOCATE_FLAG );
	AEINT32 nOldcap = m_nHashMod+1;
	AEMapPair *mpOldElem = m_mpElem;
	AEMapPair *mpNewElem = static_cast<AEMapPair*>( maAlloc.BlockAlloc( sizeof( AEMapPair )* nNewCapacity ) );

	// Make sure maAlloc succeeded
	if( mpNewElem == 0L )
		return 0;

	m_mpElem = mpNewElem;

	for( AEINT32 i = 0; i < nNewCapacity; i++ ) 
		OPS::Invalidate( (KEY &)m_mpElem[i].tKey ); 

	m_nNumElems = 0;
	m_nHashMod = nNewCapacity - 1;

	for( AEINT32 i = 0; i < nOldcap; ++i )
	{
		if( OPS::IsValid( (KEY)mpOldElem[i].tKey ) )
			Insert( maAlloc, mpOldElem[i].tKey, mpOldElem[i].tVal );
	}

	if( !bDontDeallocate )
		maAlloc.BlockFree( mpOldElem, sizeof( AEMapPair )*nOldcap );

	return 1;
}
#endif // _AEBASEMAP_INL_
